package seo.dale.util.datastructure;

public class LinkedList<E> {
	
	private int size;
	
	private Node<E> first;
	private Node<E> last;
	
	public LinkedList() {
	}

	public void addFirst(E item) {
		Node<E> oldNode = first;
		Node<E> newNode = new Node<E>(null, item, oldNode);
		first = newNode;
		if (oldNode != null) {
			oldNode.prev = newNode;
		} else {
			last = newNode; // List used to be empty.
		}
		size++;
	}
	
	public void addLast(E item) {
		Node<E> oldNode = last;
		Node<E> newNode = new Node<E>(oldNode, item, null);
		last = newNode;
		if (oldNode != null) {
			oldNode.next = newNode;
		} else {
			first = newNode; // List used to be empty.
		}
		size++;
	}
	
	public void add(int index, E item) {
		checkIndex(index);
		
		
	}
	
	private void checkIndex(int index) {
		if (index < 0 || index > size) {
			new IndexOutOfBoundsException("Index : " + index + ", Size : " + size);
		}
	}
	
	public E getFirst() {
		
		return null;
	}
	
	public E getLast() {
		
		return null;
	}
	
	public E get(int index) {
		Node<E> x;
		if (index <= size / 2) {
			x = first;
			for (int i = 0; i < index; i++) {
				x = x.next;
			}
		} else {
			x = last;
			for (int i = 0; i < size - 1 - index; i++) {
				x = x.prev;
			}
		}
		return x.item;
	}
	
	public E removeFirst() {
		
		return null;
	}
	
	public E removeLast() {
		
		return null;
	}
	
	public E remove(int index) {
		
		return null;
	}
	
	public boolean isEmpty() {
		
		return false;
	}
	
	private class Node<E> {
		Node<E> prev;
		E item;
		Node<E> next;

		Node(Node<E> prev, E item, Node<E> next) {
			this.prev = prev;
			this.item = item;
			this.next = next;
		}
	}

	@Override
	public String toString() {
		StringBuilder builder =  new StringBuilder();
		Node<E> x = first;
		for (int i = 0; i < size; i++) {
			builder.append(x.item);
			builder.append(" ");
			x = x.next;
		}
		return builder.toString();
	}

}
